CS146 Spring 2014Practice Final

To study for the final I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice final is below. Here are some facts about the actual final: (a) It is comprehensive (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) It is 10 problems, 6 problems will be on material since the midterm, four problems will come from the topics covered prior to the midterm. (f) Two problems will be exactly (less typos) off of the practice final, and one will be off of practice midterm.

One other remark about the final. All CS146 classes are being assessed this semester. As such there are a list of common question types I will need to incorporate in my final: (1) Calculate running time of a divide-and-conquer algorithm (2) Solve a recurrence with master theorem (3) Calculate the running time of algorithm given in pseudocode (4) apply an operation in an instance of an advanced data structure as well as (1) Given an instance of data )e.g. graph) and problem (MST, search shortest path), state and explain which algorithm would be best. (2) Given pseudocode of 2 algorithms (eg sort), analyze which is more efficient (3) Given a "real life" problem, figure out which algorithm or data structure would be most helpful.

1. Give the algorithms for LIST-INSERT and LIST-DELETE for a doubly linked list. Show how LIST-INSERT would insert the element 5,4,2. Show how LIST-DELETE would delete 5 from the result.
2. Briefly explain what a free space list is and what it is used for. What is the binary search tree property? Give an algorithm for listing out the elements of a BST from least to greatest.
3. Show the result of inserting 10 5 2 4 20 16 11 19 17 (in this order) into a BST using the TREE-INSERT algorithm from class. Show how TREE-DELETE would delete 11 from the result.
4. What are the red-black properties? Given an example of a red-black tree and a value such that if that value was inserted into the red black a rotation would occur.
5. Carefully state the rod-cutting problem. Give a dynamic programming algorithm that solves it.
6. State the LCS problem. What is the LCS of (1, 4, 7, 10, 13, 16) and (2, 4, 6, 7, 10, 12, 14, 16)? Show step-by-step how LENGTH-LCS would compute its table on these inputs.
7. What is a greedy algorithm? Prove always selecting the activity that finishes first will result in a solution to the activity selection problem.
8. Suppose we had a graph `G` and we wanted to determine the number of nodes in a connected component involving a vertex `v`. Suggest some algorithms we learned in class which could be used to solve this problem.
9. Consider the graph on 12 nodes that looks like a tic-tac-toe board. Label the edges not in the inner square with 2 and those in the inner square with 1. Pick the leftmost vertex in the top row of this graph. Show how Prim's algorithm would compute a spanning tree for this graph.
10. What is NP? What is NP-complete? Give an example of a problem which is provably NP-complete.